package com.chj.zhongji.class09.test01;

import java.util.HashMap;

//https://blog.csdn.net/weixin_44015043/article/details/105505020
public class Code01_LeastRecentlyUsedCache {

	public static class Node<K, V> {
		public K key;
		public V value;
		public Node<K, V> last;
		public Node<K, V> next;

		public Node(K key, V value) {
			this.key = key;
			this.value = value;
		}
	}

	public static class NodeDoubleLinkList<K, V> {
		private Node<K, V> head;
		private Node<K, V> tail;
		private HashMap<K, Node<K, V>> nodeMap;

		public NodeDoubleLinkList() {
			this.head = null;
			this.tail = null;
			this.nodeMap = new HashMap<K, Node<K, V>>();
		}

		public void addNode(Node<K, V> newNode) {
			if (newNode == null) {
				return;
			}

			if (this.head == null) {
				this.head = newNode;
				this.tail = newNode;
			} else {
				this.tail.next = newNode;
				newNode.last = this.tail;
				this.tail = newNode;
			}
			this.nodeMap.put(newNode.key, newNode);
		}

		public void moveNodeToTail(Node<K, V> node) {
			if (this.tail == node) {
				return;
			}

			if (this.head == node) {
				this.head = node.next;
				this.head.last = null;
			} else {
				node.last.next = node.next;
				node.next.last = node.last;
			}

			node.last = this.tail;
			node.next = null;
			this.tail.next = node;
			this.tail = node;
		}

		public Node<K, V> removeHead() {
			if (this.head == null) {
				return null;
			}
			Node<K, V> res = this.head;
			if (this.head == this.tail) {
				this.head = null;
				this.tail = null;
			} else {
				this.head = res.next;
				res.next = null;
				this.head.last = null;
			}
			nodeMap.remove(res.key);
			return res;
		}

		public boolean containsKey(K key) {
			return nodeMap.get(key) != null;
		}

		public Node<K, V> get(K key) {
			return nodeMap.get(key);
		}

		public int size() {
			return nodeMap.size();
		}
	}

	public static class MyCache<K, V> {
		private NodeDoubleLinkList<K, V> nodeList;
		private int capacity;

		public MyCache(int capacity) {
			if (capacity < 1) {
				throw new RuntimeException("should be more than 0.");
			}
			this.nodeList = new NodeDoubleLinkList<K, V>();
			this.capacity = capacity;
		}

		public V get(K key) {
			if (this.nodeList.containsKey(key)) {
				Node<K, V> res = this.nodeList.get(key);
				this.nodeList.moveNodeToTail(res);
				return res.value;
			}
			return null;
		}

		public void set(K key, V value) {
			if (this.nodeList.containsKey(key)) {
				Node<K, V> node = this.nodeList.get(key);
				node.value = value;
				this.nodeList.moveNodeToTail(node);
			} else {
				Node<K, V> newNode = new Node<K, V>(key, value);
				this.nodeList.addNode(newNode);
				if (nodeList.size() == this.capacity + 1) {
					this.nodeList.removeHead();
				}
			}
		}
	}

	public static void main(String[] args) {
//		MyCache<String, Integer> testCache = new MyCache<String, Integer>(3);
//		testCache.set("A", 1);
//		testCache.set("B", 2);
//		testCache.set("C", 3);
//		System.out.println(testCache.get("B"));
//		System.out.println(testCache.get("A"));
//		testCache.set("D", 4);
//		System.out.println(testCache.get("D"));
//		System.out.println(testCache.get("C"));

		MyCache<Integer, Integer> cache = new MyCache<Integer, Integer>(2 /* 缓存容量 */ );

		cache.set(1, 1);
		cache.set(2, 2);
		cache.get(1); // 返回 1
		cache.set(3, 3); // 该操作会使得密钥 2 作废
		// 为什么这里不是1作废呢，是因为对于1来说尽管先于2进行插入，但是对于1有新的get操作，这个操作就算是对进行了一个操作，所以这个时候2是最远没有进行操作的数。
		cache.get(2); // 返回 -1 (未找到)
		cache.set(4, 4); // 该操作会使得密钥 1 作废
		cache.get(1); // 返回 -1 (未找到)
		System.out.println(cache.get(3)); // 返回 3
		System.out.println(cache.get(4)); // 返回 4

		System.out.println();
//		[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
//		[1,-1]
		MyCache<Integer, Integer> cache2 = new MyCache<Integer, Integer>(3 /* 缓存容量 */ );

		cache2.set(1, 1);
		cache2.set(2, 2);
		cache2.set(3, 2);
		System.out.println(cache2.get(1)); // 返回 1
		cache2.set(4, 4); // 该操作会使得密钥 2 作废
		// 为什么这里不是1作废呢，是因为对于1来说尽管先于2进行插入，但是对于1有新的get操作，这个操作就算是对进行了一个操作，所以这个时候2是最远没有进行操作的数。
		System.out.println(cache2.get(2)); // 返回 -1 (未找到)
//		cache.set(4, 4); // 该操作会使得密钥 1 作废
//		cache.get(1); // 返回 -1 (未找到)
//		System.out.println(cache.get(3)); // 返回 3
//		System.out.println(cache.get(4)); // 返回 4
	}

}
